---
title: "选数"
created: 2025-11-28
tags:
  - 算法
---

# 选数

## 题目 [选数](https://www.luogu.com.cn/problem/P1036)

![[image-d24fe65e.png]]

## 思路分析

求组合数 如果不剪枝的话 其实就和前面的全排列差不多

甚至还不需要标记某个数用没用过 因为后一个数必须比前一个数大 所以一定不会被用过

这题就是先做出组合数 然后判断是否为素数（试除法）

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=25;
int a[N];
int way[N];
int n,k;
int res;

bool is_prime(int x){
	if(x<2) return false;
	for(int i=2;i<=x/i;i++){
		if(x%i==0){
			return false;
		}
	}
	return true;
}

void dfs(int u,int start){
	if(u==k+1){
		int sum=0;
		for(int i=1;i<=k;i++){
			sum+=way[i];
		}
		if(is_prime(sum))
			res++;
		return;
	}

	for(int i=start;i<=n;i++){
		way[u]=a[i];
		dfs(u+1,i+1);
		way[u]=0;
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	dfs(1,1);
	cout<<res;
	return 0;
 }
```

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=25;
int a[N];
int way[N];
int n,k;
int res;

bool is_prime(int x){
	if(x<2) return false;
	for(int i=2;i<=x/i;i++){
		if(x%i==0){
			return false;
		}
	}
	return true;
}

void dfs(int u,int start){
    if(u+n-start<k) //剪枝(后续位置不够放)
        return;

	if(u==k+1){
		int sum=0;
		for(int i=1;i<=k;i++){
			sum+=way[i];
		}
		if(is_prime(sum))
			res++;
		return;
	}

	for(int i=start;i<=n;i++){
		way[u]=a[i];
		dfs(u+1,i+1);
		way[u]=0;
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dfs(1,1);
	cout<<res;
	return 0;
 }
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/DFS BFS相关模型/DFS/组合型（n中选m 不考虑顺序）/组合数|组合数]] 🏠 [[00-刷题理模型]] ➡️ [[转载|转载]]